机器学习中的维度灾难

导读

对于一个高维空间中的球体，将这个球的外壳去掉薄薄的一层，这个球的体积还剩原来的多少？本文以这个问题为引子，尝试探讨机器学习中的维度灾难，欢迎同行指正或拍砖。

由于编辑器不支持公式编辑，公式较多的地方，用截图代替。高维空间中的球体人类生活在三维空间，大脑的直觉也以三维空间为参考系建立，到了高维空间这种直觉就不再起作用，甚至在潜意识里形成误导。回到导读中的高维球体的问题，我们将其转化为如下形式。

从上述例子中可以得到如下推论：

     在高维空间中，假如样本在空间中是均匀分布的，那么绝大多数的样本都稀疏地分布在球的表面附近。

高维空间中的局部方法

假设在特征空间中，基于目标点局部的观测，可以很好地预测出目标点的特性，此类方法称为局部方法。典型的局部方法有近邻方法和核方法，这两种方法在高维空间中都会遇到问题。

近邻方法（kNN：knearest neighbors）

该方法的思想是：对样本空间中一个新的输入x（称为目标点）进行预测时，先找到空间中距x最近的k个已知样本（称为k个近邻），并用这k个样本对应的输出来产生预测结果。如果是分类问题，就进行多数投票；如果是回归问题，就对k个输出进行平均。

上述逻辑似乎无懈可击，因为即便是高维空间也总能找到离目标点最近的k个样本吧？但其实kNN有一个容易被忽略的隐含假设，即k个最近的样本离目标点都不能太远。在低维空间中，这是很容易满足的；但在高维空间却并非如此。结合上面高维空间中球体的例子，来考虑下面的问题。

核方法

与近邻方法相对应的，是核方法。核方法是在目标点周围先选择一个半径固定的邻域，邻域里有几个样本算几个样本，用来估计目标点的值。显然，核方法在高维空间中遇到的问题是，在目标点的邻域里可能根本找不到样本点，因此无法做出有效估计。

高维空间的划分

有一些机器学习算法，有赖于对空间的划分。其主要思想是先将整个输入空间划分为足够小的子空间，小到每个子空间里的模式都足够简单，这样就可以在局部进行简单建模。以决策树为例，它通过自上而下的二分过程，将整个输入空间（或特征空间）划分为一系列的小区间（树的叶子节点），然后在这些小区间上直接用常量建模。另外一个例子是非参数密度估计，下面以此为例进行详细介绍。

非参数密度估计

假设，我们要对下图中某一个位置的点进行分类预测，判断其颜色。

非参数密度估计的想法很简单，首先将整个区间划分为如图的16个小区间，在每个小区间中属于某种颜色的概率用频率来代替。那么对于图中画×的点，预测如下：

最后会预测为红色。

这种方法的问题在于，随着空间维度的增加，子区间的个数指数增加。必须确保子区间中有样本点才能进行预测，那么需要的样本点也会指数增加。用图示例如下：

基于空间划分的方法，本质上是把整体模式的复杂性转移到了空间划分的复杂性上。因为指数是爆炸增长的，所需样本点的个数也会成爆炸趋势，且不说实际根本没有足够多的样本，即便有了这些样本，样本的存储也是个问题。因此，这种在低维空间中很朴素很好用的方法，在高维空间中就形成了灾难。

高维空间中的基函数方法

还记得函数的taylor展开式吗？这说明只要函数在某一点的各阶导数存在，就可以在该点附近用一组多项式函数来近似表达原函数。这种情况下，多项式函数就形成了一组基函数。类似的，傅里叶级数则是用三角函数来作为基。

从函数拟合的角度来理解机器学习模型，自然就有了机器学习中的基函数方法。我们在此以多项式基函数为例，说明基函数方法在高维空间中应用的困难。

多项式基函数方法总结

从上面的这些例子可以看出，我们在低维空间中建立的很多直觉，无法直接类推到高维空间。而在机器学习领域，高维特征是相当常见的。随着特征空间维度的增加，样本空间分布的稀疏程度、模型的复杂度和算法的计算量一般都会指数增长，这给机器学习领域的采样、计算和存储都带来了很大的困难，我们称之为“维度灾难”。

如何理解维度灾难的本质呢？假设平均每个特征维度的变量，平均可以取N种不同的值（对连续值的情况，对应该维度上空间的N个划分），那么D个维度变量组合的结果就是N的D次方。这个组合数是呈指数增长的，这种现象被称为“组合爆炸”。也就是说，在特征空间中每增加一个维度，都需要在先前的基础上成倍地增加尝试所有组合方式对结果的影响。组合爆炸之时，也就形成了灾难。

对于高维空间给机器学习带来的这些“灾难性”的后果，我们又该如何应对呢？一般可以考虑以下思路：

降维：如果不同维度之间存在线性相关的关系，或者数据集在某些维度上相对于另外的维度方差很小，可以用PCA或LDA等方法先进行降维，然后转化到低维空间再进行处理。

优化计算：虽然空间维度理论上带来计算量的指数增长，但通常可以利用模型的实际特性来优化计算。比如，变量的对称性（如FM：Factorization Machine），或空间距离的三角不等式（如kNN）等。

选择更适用于高维空间的方法：比如，同样是基函数方法，不同于多项式基函数的是，MARS（Multivariate Adaptive Regression Splines）使用分段线性的基函数，可以将基函数的数量降低到2N*D（N为样本数量，D为特征空间维度）。

参考文献

《The Elements of  Statistical Learning: Data Mining, Inference, and Prediction》，Second Edition，Jerome Friedman

《Pattern Recognition and Machine Learning》，Bishop

往期精彩回顾【年会刚过，你中奖了吗？】在线抽奖活动中如何实现中奖概率的自适应调整罗素的理发师和奥卡姆剃刀
互联网从业人必须知道的「用户行为数据收集系统」
用户行为数据收集系统--(2)客户端SDK设计
用户行为数据收集系统--(3)数据接收端设计

更多精彩内容

长按扫码可关注